|
A division algorithm is an algorithm which, given two integers N and D, computes their quotient and/or remainder, the result of division. Some are applied by hand, while others are employed by digital circuit designs and software. Division algorithms fall into two main categories: slow division and fast division. Slow division algorithms produce one digit of the final quotient per iteration. Examples of slow division include restoring, non-performing restoring, non-restoring, and SRT division. Fast division methods start with a close approximation to the final quotient and produce twice as many digits of the final quotient on each iteration. Newton–Raphson and Goldschmidt fall into this category. Discussion will refer to the form , where * ''N'' = Numerator (dividend) * ''D'' = Denominator (divisor) is the input, and * ''Q'' = Quotient * ''R'' = Remainder is the output. ==Division by repeated subtraction== The simplest division algorithm, historically incorporated into a greatest common divisor algorithm presented in Euclid's ''Elements'', Book VII, Proposition 1, finds the remainder given two positive integers using only subtractions and comparisons: while N ≥ D do N := N - D end return N The proof that the quotient and remainder exist and are unique, described at Euclidean division, gives rise to a complete division algorithm using additions, subtractions, and comparisons: function divide(N, D) if D = 0 then error(DivisionByZero) end if D < 0 then (Q,R) := divide(N, -D); return (-Q, R) end if N < 0 then (Q,R) := divide(-N, D) if R = 0 then return (-Q, 0) else return (-Q - 1, D - R) end end -- At this point, N ≥ 0 and D > 0 Q := 0; R := N while R ≥ D do Q := Q + 1 R := R - D end return (Q, R) end This procedure always produces R ≥ 0. Although very simple, it takes Ω(Q) steps, and so is exponentially slower than even slow division algorithms like long division. It is useful if Q is known to be small (being an output-sensitive algorithm), and can serve as an executable specification. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「division algorithm」の詳細全文を読む スポンサード リンク
|